2941.
Дима и массив
Мама подарила
мальчику Диме массив длины n. Массив
этот не простой, а особенный. Дима может выбрать два числа i и d (1 ≤ i ≤ n, -1000 ≤ d
≤ 1000), и элемент с индексом i
магически становится равным d. Дима
играет со своим массивом, а мама время от времени задает ему вопросы – какова
сумма всех чисел в массиве с индексами от f
до t? Дима легко справился с этими
вопросами, сможете ли Вы?
Вход. В первой строке находятся два целых числа n и q
(1 ≤ n ≤ 5·105,
1 ≤ q ≤ 105) –
количество элементов в массиве и суммарное количество операций и запросов
соответственно. В следующей строке дано n
чисел a1, a2, ..., an (-1000 ≤ ai
≤ 1000) – начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может
быть = или ?. Если строка начинается с =, то это операция присваивания. Далее
следуют i и d, ограничения на которые описаны в условии. Если строка начинается
с ?, то это запрос. Далее следуют числа f
и t (1 ≤ f, t ≤ n).
Выход. Для каждого запроса выведите сумму чисел в массиве с
индексами от f до t, по одному результату в строке.
|
Пример
входа |
Пример
выхода |
|
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3 |
6 5 |
РЕШЕНИЕ
структуры данных – дерево отрезков
Анализ алгоритма
Для решения
задачи следует реализовать дерево отрезков, поддерживающее модификацию
единичного элемента и суммирование.
Пример
Промоделируем
запросы, приведенные в примере.
Реализация алгоритма
Дерево отрезков храним в векторе SegTree длины 4*MAX, где MAX
– максимальное количество элементов, которое может храниться в отрезке.
#define MAX 500000
vector<int>
SegTree(4*MAX,0);
На вход функции BuildTree построения дерева отрезков передается массив a, номер
текущей вершины дерева v и границы
отрезка lpos и rpos,
соответствующие вершине v.
void BuildTree(vector<int>&a, int v, int
lpos, int
rpos)
{
Если вершине v соответствует отрезок, состоящий из одного элемента (lpos = rpos), то мы дошли
до листа дерева отрезков. Присваиваем ему значение alpos.
if (lpos == rpos) SegTree[v] = a[lpos];
else
{
Находим середину
отрезка mid = (lpos + rpos) / 2.
int mid = (lpos + rpos) / 2;
Разбиваем
отрезок [left; right] на [left; mid] и [mid + 1; right]. Запускаем
рекурсивно построение дерева отрезков на подотрезках.
BuildTree(a, 2*v, lpos, mid);
BuildTree(a, 2*v+1, mid + 1, rpos);
Пересчитываем
значение суммы в текущей вершине дерева отрезков.
SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
}
}
Функция Update присваивает элементу с индексом pos значение val.
Вершине v соответствует отрезок [lpos; rpos].
void Update(int v, int
lpos, int
rpos, int pos, int val)
{
Если вершине v соответствует отрезок, состоящий из одного элемента (lpos = rpos), то мы дошли
до листа дерева отрезков. Присваиваем ему значение val.
if (lpos == rpos) SegTree[v] = val;
else
{
Иначе вычисляем, в каком – левом или
правом сыне вершины v лежит элемент с
индексом pos. Запускаем
рекурсивно его модификацию.
int mid = (lpos + rpos) / 2;
if (pos <= mid)
Update (2*v, lpos, mid, pos, val);
else
Update (2*v+1, mid+1, rpos, pos, val);
Пересчитываем значение суммы в текущей
вершине дерева отрезков.
SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
}
}
Функция Summa
возвращает значение суммы на отрезке [left; right].
Вершине v соответствует отрезок [lpos; rpos].
int Summa(int v, int
lpos, int rpos, int left, int right)
{
if (left > right) return 0;
Если отрезок [left; right] совпадает с отрезком [lpos; rpos], который хранится в вершине v дерева, то возвращаем находящееся
в ней значение суммы.
if ((left == lpos) && (right == rpos))
return SegTree[v];
Находим середину отрезка mid = (lpos + rpos)
/ 2.
int mid = (lpos + rpos) / 2;
Разбиваем отрезок [left; right] на [left; mid] и [mid + 1; right]. Запускаем
рекурсивно вычисление сумм на подотрезках. Складываем полученные суммы.
return Summa(2*v, lpos, mid, left, min(right,mid)) +
Summa(2*v+1, mid+1, rpos, max(left,mid+1), right);
}
Основная часть
программы. Читаем входные данные.
scanf("%d
%d",&n,&q);
v.resize(n+1);
for(i = 1; i <= n; i++)
scanf("%d",&v[i]);
scanf("\n");
По данным в массиве v строим дерево
отрезков.
BuildTree(v,1,1,n);
Последовательно обрабатываем q запросов. В зависимости от типа
запроса производим либо модификацию элемента, либо вычисление суммы на отрезке.
for(j = 0; j < q; j++)
{
scanf("%c ",&c);
if (c == '=')
{
scanf("%d %d\n",&i,&d);
Update(1,1,n,i,d);
} else
{
scanf("%d %d\n",&f,&t);
printf("%d\n",Summa(1,1,n,f,t));
}
}
Реализация алгоритма – iostream
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> SegTree;
void BuildTree(vector<int>& a, int Vertex, int LeftPos, int RightPos)
{
if (LeftPos == RightPos)
SegTree[Vertex] = a[LeftPos];
else
{
int Middle = (LeftPos + RightPos) / 2;
BuildTree(a, 2 * Vertex, LeftPos, Middle);
BuildTree(a, 2 * Vertex + 1, Middle +
1, RightPos);
SegTree[Vertex] = SegTree[2 * Vertex] + SegTree[2 * Vertex + 1];
}
}
int Summa(int Vertex, int LeftPos, int RightPos, int Left, int Right)
{
if (Left > Right) return 0;
if ((Left == LeftPos) && (Right == RightPos))
return SegTree[Vertex];
int Middle = (LeftPos + RightPos) / 2;
return Summa(2 * Vertex, LeftPos, Middle, Left, min(Right, Middle)) + Summa(2 * Vertex + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right);
}
void update(int Vertex, int LeftPos, int RightPos, int Position, int NewValue)
{
if (LeftPos == RightPos)
SegTree[Vertex] = NewValue;
else
{
int Middle = (LeftPos + RightPos) / 2;
if (Position <= Middle) update(2
* Vertex, LeftPos, Middle, Position, NewValue);
else update(2 * Vertex + 1, Middle + 1, RightPos, Position, NewValue);
SegTree[Vertex] = SegTree[2 * Vertex] + SegTree[2 * Vertex + 1];
}
}
vector<int> v;
int n, q, i, d, p, f, t;
char c;
int main(void)
{
cin >> n >> q;
v.resize(n + 1);
SegTree.resize(4 * n + 1);
for (i = 1; i <= n;
i++)
cin >> v[i];
BuildTree(v, 1, 1, n);
for (i = 0; i < q; i++)
{
cin >> c;
if (c == '=')
{
cin
>> p >> d;
update(1, 1, n, p, d);
}
else
{
cin >> f >> t;
cout << Summa(1, 1, n, f, t) << endl;
}
}
return 0;
}
Реализация алгоритма – класс
#include <cstdio>
#include <vector>
#define MAX 500000
using namespace std;
class SegmentTree
{
public:
vector<int> SegTree;
int len;
SegmentTree(int n)
{
len = n;
SegTree.resize(4*n);
}
SegmentTree(vector<int> &v)
{
len = (int) v.size();
SegTree.resize(4*len);
BuildTree(v,1,0,len-1);
}
void BuildTree(vector<int>&a,
int v, int tl, int tr)
{
if (tl == tr) SegTree[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
BuildTree(a, v*2, tl, tm);
BuildTree(a, v*2+1, tm+1, tr);
SegTree[v] = SegTree[v*2] + SegTree[v*2+1];
}
}
int Summa(int Left, int Right)
{
return Summa(1,0,len-1,Left,Right);
}
int Summa(int v, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left > Right) return 0;
if ((Left == LeftPos) && (Right
== RightPos)) return SegTree[v];
int Middle = (LeftPos + RightPos) / 2;
return Summa(v*2, LeftPos, Middle, Left,
min(Right,Middle)) +
Summa(v*2+1,
Middle+1, RightPos, max(Left,Middle+1), Right);
}
void update(int
Position, int NewValue)
{
update(1,0,len-1,Position,NewValue);
}
void update(int v, int LeftPos, int
RightPos,
int Position, int NewValue)
{
if (LeftPos == RightPos) SegTree[v] =
NewValue;
else
{
int Middle = (LeftPos + RightPos) / 2;
if (Position <= Middle)
update (v*2, LeftPos, Middle, Position, NewValue);
else
update (v*2+1, Middle+1, RightPos, Position, NewValue);
SegTree[v] = SegTree[v*2] + SegTree[v*2+1];
}
}
};
vector<int>
v;
int n, q, i, j, d, f, t;
char c;
int main(void)
{
scanf("%d %d\n",&n,&q);
v.resize(n+1);
for(i = 1; i <= n; i++) scanf("%d",&v[i]); scanf("\n");
SegmentTree s(v);
for(j = 0; j < q; j++)
{
scanf("%c ",&c);
if (c == '=')
{
scanf("%d %d\n",&i,&d);
s.update(i,d);
} else
{
scanf("%d %d\n",&f,&t);
printf("%d\n",s.Summa(f,t));
}
}
return 0;
}
Реализация алгоритма – динамическое выделение памяти new /
delete
#include <cstdio>
#include <algorithm>
using namespace std;
int *SegTree;
void BuildTree(int *a, int Vertex, int
LeftPos, int RightPos)
{
if (LeftPos == RightPos)
SegTree[Vertex] = a[LeftPos];
else
{
int Middle = (LeftPos + RightPos) / 2;
BuildTree(a, 2*Vertex, LeftPos, Middle);
BuildTree(a, 2*Vertex+1, Middle+1, RightPos);
SegTree[Vertex] = SegTree[2*Vertex] + SegTree[2*Vertex+1];
}
}
int Summa(int Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left > Right) return
0;
if ((Left == LeftPos) && (Right == RightPos))
return SegTree[Vertex];
int Middle = (LeftPos + RightPos) / 2;
return Summa(2*Vertex, LeftPos, Middle, Left,
min(Right,Middle)) +
Summa(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);
}
void update(int Vertex, int LeftPos, int
RightPos,
int Position, int NewValue)
{
if (LeftPos == RightPos)
SegTree[Vertex] = NewValue;
else
{
int Middle = (LeftPos + RightPos) / 2;
if (Position <= Middle)
update
(2*Vertex, LeftPos, Middle, Position, NewValue);
else
update (2*Vertex+1, Middle+1, RightPos, Position, NewValue);
SegTree[Vertex] = SegTree[2*Vertex] + SegTree[2*Vertex+1];
}
}
int n, q, i, j, d, f, t;
char c;
int main(void)
{
scanf("%d %d\n",&n,&q);
int *v = new int[n+1];
for(i = 1; i <= n; i++)
scanf("%d",&v[i]);
scanf("\n");
SegTree = new int[4*n];
BuildTree(v,1,0,n);
delete[] v;
for(j = 0; j < q; j++)
{
scanf("%c ",&c);
if (c == '=')
{
scanf("%d %d\n",&i,&d);
update(1,0,n,i,d);
} else
{
scanf("%d %d\n",&f,&t);
printf("%d\n",Summa(1,0,n,f,t));
}
}
delete[] SegTree;
return 0;
}